home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / incl / LEDA.020+881 / graph_alg.h < prev    next >
C/C++ Source or Header  |  1994-08-05  |  6KB  |  188 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  graph_alg.h
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16. #ifndef LEDA_GRAPHALG_H
  17. #define LEDA_GRAPHALG_H
  18.  
  19. #include <LEDA/graph.h>
  20. #include <LEDA/ugraph.h>
  21. #include <LEDA/node_matrix.h>
  22.  
  23.  
  24. //-----------------------------------------------------------------------------
  25. // basic graph algorithms:
  26. //-----------------------------------------------------------------------------
  27.  
  28. bool        TOPSORT(const graph& G, node_array<int>& ord);
  29.  
  30. bool        TOPSORT1(graph& G);
  31.  
  32. list<node>  DFS(const graph& G, node s, node_array<bool>& reached) ;
  33.  
  34. list<node>  BFS(const graph& G, node s, node_array<int>& dist);
  35.  
  36. list<edge>  DFS_NUM(const graph& G, node_array<int>& dfsnum, 
  37.                                     node_array<int>& compnum);
  38.  
  39. int         COMPONENTS(const ugraph& G, node_array<int>& compnum);
  40.  
  41. int         COMPONENTS1(const ugraph& G, node_array<int>& compnum);
  42.  
  43. int         STRONG_COMPONENTS(const graph& G, node_array<int>& compnum);
  44.  
  45. int         STRONG_COMPONENTS1(const graph& G, node_array<int>& compnum);
  46.  
  47. int         BICONNECTED_COMPONENTS(const ugraph& G, edge_array<int>& compnum);
  48.  
  49. graph       TRANSITIVE_CLOSURE(const graph& G);
  50.  
  51.  
  52.  
  53. //-----------------------------------------------------------------------------
  54. // shortest paths:
  55. //-----------------------------------------------------------------------------
  56.  
  57. void DIJKSTRA(const graph& G, node s, const edge_array<int>& cost, 
  58.                                             node_array<int>& dist, 
  59.                                             node_array<edge>& pred);
  60.  
  61. bool BELLMAN_FORD(const graph& G, node s, const edge_array<int>& cost,
  62.                                                 node_array<int>& dist,
  63.                                                 node_array<edge>& pred);
  64.  
  65. bool ALL_PAIRS_SHORTEST_PATHS(graph& G, const edge_array<int>&  cost,
  66.                                               node_matrix<int>& dist);
  67.  
  68.  
  69.  
  70.  
  71. //-----------------------------------------------------------------------------
  72. // maximum flow:
  73. //-----------------------------------------------------------------------------
  74.  
  75.  
  76. int  MAX_FLOW(graph& G, node s, node t, const edge_array<int>& cap,
  77.                                               edge_array<int>& flow);
  78.  
  79. //-----------------------------------------------------------------------------
  80. // min cost flow:
  81. //-----------------------------------------------------------------------------
  82.  
  83. int MIN_COST_MAX_FLOW(graph& G, node s, node t, const edge_array<int>& cap,
  84.                                                 const edge_array<int>& cost,
  85.                                                 edge_array<int>& flow);
  86.  
  87.  
  88. //-----------------------------------------------------------------------------
  89. // matchings:
  90. //-----------------------------------------------------------------------------
  91.  
  92. // Edmond's algorithm
  93.  
  94. list<edge> MAX_CARD_MATCHING(graph& G, int heur = 1);    
  95.  
  96.  
  97. // Hopcroft/Karp
  98.  
  99. list<edge> MAX_CARD_BIPARTITE_MATCHING(graph& G, const list<node>& A, const list<node>& B);
  100.  
  101. list<edge> MAX_CARD_BIPARTITE_MATCHING(graph& G);
  102.  
  103. list<edge> MAX_CARD_BIPARTITE_MATCHING1(graph& G, const list<node>& A, const list<node>& B);
  104.  
  105. list<edge> MAX_CARD_BIPARTITE_MATCHING1(graph& G);
  106.  
  107.  
  108.  
  109. list<edge> MAX_WEIGHT_BIPARTITE_MATCHING(graph& G, const list<node>&A, 
  110.                                                    const list<node>&B,
  111.                                                    const edge_array<int>&);
  112.  
  113.  
  114.  
  115.  
  116. //-----------------------------------------------------------------------------
  117. // spanning trees:
  118. //-----------------------------------------------------------------------------
  119.  
  120. list<edge> SPANNING_TREE(const graph& G);
  121.  
  122. list<edge> MIN_SPANNING_TREE(const graph& G, const edge_array<int>& cost);
  123.  
  124. list<edge> MIN_SPANNING_TREE(const ugraph& G, const edge_array<int>& cost);
  125.  
  126.  
  127.  
  128. //-----------------------------------------------------------------------------
  129. // planar graphs
  130. //-----------------------------------------------------------------------------
  131.  
  132. bool PLANAR(graph&, bool embed=false);
  133.  
  134. bool PLANAR(graph&, list<edge>&, bool embed=false);
  135.  
  136. void make_biconnected_graph(graph&G);
  137.  
  138. list<edge> TRIANGULATE_PLANAR_MAP(graph&);
  139.  
  140. int STRAIGHT_LINE_EMBEDDING(graph& G,node_array<int>& xcoord,
  141.                                      node_array<int>& ycoord);
  142.  
  143. int STRAIGHT_LINE_EMBEDDING2(graph& G,node& a, node& b, node& c,
  144.                              node_array<int>& xcoord,node_array<int>& ycoord);
  145.  
  146.  
  147. //-----------------------------------------------------------------------------
  148. // "REAL" versions 
  149. //-----------------------------------------------------------------------------
  150.  
  151.  
  152. void DIJKSTRA(const graph& G, node s, const edge_array<double>& cost, 
  153.                                             node_array<double>& dist, 
  154.                                             node_array<edge>& pred);
  155.  
  156. bool BELLMAN_FORD(const graph& G, node s, const edge_array<double>& cost,
  157.                                                 node_array<double>& dist,
  158.                                                 node_array<edge>& pred);
  159.  
  160.  
  161. bool ALL_PAIRS_SHORTEST_PATHS(graph& G, const edge_array<double>&  cost,
  162.                                               node_matrix<double>& dist);
  163.  
  164.  
  165. double MAX_FLOW(graph& G, node s, node t, const edge_array<double>& cap,
  166.                                                 edge_array<double>& flow);
  167.  
  168.  
  169. list<edge> MAX_WEIGHT_BIPARTITE_MATCHING(graph& G, const list<node>&, 
  170.                                                    const list<node>&,
  171.                                                    const edge_array<double>&);
  172.  
  173.  
  174.  
  175. int STRAIGHT_LINE_EMBEDDING(graph& G,node_array<double>& xcoord,
  176.                                      node_array<double>& ycoord);
  177.  
  178. int STRAIGHT_LINE_EMBEDDING2(graph& G,node_array<double>& xcoord,
  179.                                       node_array<double>& ycoord);
  180.  
  181.  
  182. list<edge> MIN_SPANNING_TREE(const graph& G, const edge_array<double>& cost);
  183.  
  184. list<edge> MIN_SPANNING_TREE(const ugraph& G, const edge_array<double>& cost);
  185.  
  186.  
  187. #endif
  188.